/*
 * =====================================================================================
 *
 *       Filename:  tree23.hpp
 *
 *    Description:  2-3树的实现
 *
 *        Version:  1.0
 *        Created:  2017年05月02日 21时27分48秒
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  Crane (), 215379951@qq.com
 *   Organization:  Free Src
 *
 * =====================================================================================
 */

/* 关于C++模板使用
 * 模板使用总结: 在template类中的T相关类型, 都可以被typedef.
 * 比如 T类型的比较函数指针, T类型的指针等.
 *
 * 如果在 类外要使用T 类型指针, 比如函数中. 将函数定义为模板函数即可.
 */

/*
 * 关于2-3树说明
 * 一棵树用一个Tree23_Node 类型指针表示.
 * Tree23_Slot 表示2
 */


#ifndef  tree23_H_
#define  tree23_H_

#include <iostream>
#include <assert.h>
#include <string.h>


// 比较函数返回值.
typedef int comp_t;

const int COMP_GT =  1;
const int COMP_EQ =  0;
const int COMP_LE = -1;

// 函数返回值.
const int kTREE23_SUC        =  0;          // 成功
const int kTREE23_ERR        = -1;          // 内部错误

const int kTREE23_UNKNOW_ERR = -100;        // 未错误, 比如程序流程执行到了不该执行的地方

const int kTREE23_EXIST      = -200;        // 插入时, key已存在
const int kTREE23_MEMORY     = -201;        // 没有足够的内存可用


// 前置声明, 在 Tree23_Slot 中要用到Tree23_Node类型的指针.
template <class T>
class Tree23_Node;

template <class T>
class  Tree23_Slot;

template <class T>
class  ExplodeNode;


// 必须: T 类型需要重载 >, ==, < 操作符号, 还要支持拷贝构造
template <class T>
class  Tree23
{
public:
    typedef Tree23_Node<T>   *PNode;        // 指向Tree23_Node 类型的指针指向Tree23_Node 类型的指针.
    typedef Tree23_Node<T>    Node;

private:
    PNode    root;
    PNode newRoot;

public:
    Tree23( ) {
        root    = NULL;
        newRoot = NULL;
    }

    int Insert(T ele) {
        int ret = 0;
        ret = root->Insert(ele, newRoot);

        if (ret != kTREE23_SUC)
            return ret;

        if ( NULL == newRoot )
            return ret;

        root = newRoot;
        newRoot = NULL;

        return ret;
    }

    bool Find(T ele) {
        PNode findNode;
        return root->Find(ele, findNode);
    }

    // T ele要支持遍历打印数据, 需要重载 std::cout << 操作符号.
    void Traversal() {
        root->Traversal();
    }

};

template <class T>
class Tree23_Node
{
public:
    typedef Tree23_Node<T>   *Tree;         // 用 Tree23_Node指针类型表示2-3 树.
    typedef Tree23_Node<T>   *SubTree;      // 用 Tree23_Node指针类型表示2-3子树.
    typedef Tree23_Node<T>   *PNode;        // 指向Tree23_Node 类型的指针指向Tree23_Node 类型的指针.
    typedef Tree23_Node<T>    Node;
    typedef Tree23_Slot<T>    Slot;

    typedef ExplodeNode<T>    ExpNode;      // 一颗即将爆裂的节点.

public:
    // 成员: 2个Slot元素, 三颗子树, 1个指向父节点的指针.
    Slot       m_leftSlot;
    Slot       m_rightSlot;

    SubTree m_parent;               // m_parent 父节点
    SubTree m_leftTree;             // 左子树
    SubTree m_midTree;              // 中子树
    SubTree m_rightTree;            // 右子树

public:
    Tree23_Node()
    {
        initResource();
    }

    Tree23_Node(T leftEle) : m_leftSlot(leftEle)
    {
        initResource();
    }

    Tree23_Node(T leftEle, T rightEle) : m_leftSlot(leftEle), m_rightSlot(rightEle)
    {
        initResource();
    }


    /*
     * 先查询是否存在节点, 如果不存在, 再插入.
     * 插入后, 如果树根改变, 返回修改后的树根.
     * 否则传入newRoot不做修改.
     */
    int Insert(T ele, Tree &newRoot)
    {
        PNode findNode;
        bool  isExist = Find(ele, findNode);

        if (isExist)
            return kTREE23_EXIST;

        // 如果不存在, 那么将新生成的节点插入到 findNode中(内部可能涉及到节点的分裂和向上移动操作)
        // tips: findNode, 一定位于树的最底层.
        //     : new出来的节点, 就不要费心了, 由被调用者释放.
        return findNode->InsertNode(new Node(ele), newRoot);
    }

    //   找到: 返回true, 返回ele所在节点的指针
    // 未找到: 返回false, 返回最终终止的节点的指针
    bool Find(T ele, PNode &findNode)
    {
        //assert(this != NULL);           // 不要在空树上查询一个节点, 后期可能会允许, 并返回NULL
        if (NULL == this)
        {
            findNode = NULL;
            return false;
        }

        findNode = this;

        if ( isEmptySlot() )
            return false;

        // 下面是 one slot情况: 当前节点至少有一个左元素.
        if ( m_leftSlot.IsEquel(ele) )
            return true;

        if ( ele < m_leftSlot.GetEle() )
            return leftFind(ele, findNode);

        if ( isOneSlot() )
            return midFind(ele, findNode);

        // 下面是full slot 情况
        if ( m_rightSlot.IsEquel(ele) )
            return true;

        if ( ele > m_rightSlot.GetEle() )
            return rightFind(ele, findNode);

        if ( ele < m_rightSlot.GetEle() )
            return midFind(ele, findNode);

        assert(false);             // 程序逻辑正确的话, 不会执行到这里, 因为i前面将情况都列举完了.
        return kTREE23_UNKNOW_ERR;
    }

public:

    void SetLeftSlot(Slot slot)
    {
        slot.Move2(m_leftSlot);
    }

    void SetRightSlot(Slot slot)
    {
        slot.Move2(m_rightSlot);
    }

    void SetSlot(Slot sl, Slot sr)
    {
        SetLeftSlot(sl);
        SetRightSlot(sr);
    }

    void Traversal()
    {
        subTreeTravesal(m_leftTree);

        m_leftSlot.Show();

        subTreeTravesal(m_midTree);

        if (isFullSlot())
        {
            m_rightSlot.Show();
            subTreeTravesal(m_rightTree);
        }
    }

    // 要定义为private函数
    void subTreeTravesal(SubTree subTree)
    {
        if (NULL != subTree )
            subTree->Traversal();
    }

public:

    // 父子关系是相互的
    void SetTree(SubTree lt, SubTree mt, SubTree rt)
    {
        SetLeftTree(lt);
        SetMidTree(mt);
        SetRightTree(rt);
    }

    void SetLeftTree(SubTree subTree)
    {
        // 父子关系是相互的
        m_leftTree = subTree;
        if( NULL != subTree )
            subTree -> m_parent = this;
    }

    void SetMidTree(SubTree subTree)
    {
        m_midTree = subTree;
        if( NULL != subTree )
            subTree -> m_parent = this;
    }

    void SetRightTree(SubTree subTree)
    {
        m_rightTree = subTree;
        if( NULL != subTree )
            subTree -> m_parent = this;
    }

    void SetParentTree(SubTree subTree)
    {
        m_parent = subTree;
    }

public:

    void TreeAssert()
    {
        if(NULL != m_leftTree)
            assert(m_leftTree->m_parent == this);

        if(NULL != m_midTree)
            assert(m_midTree->m_parent == this);

        if(NULL != m_rightTree)
            assert(m_rightTree->m_parent == this);
    }

private:        // InsertNode 相关

    // 在当前节点上, 插入gUpNode:
    // 命名"pUpNode"是因为这个节点是下面节点上升而来
    // 内部操作有: 分裂节点, 递归向上继续插入分裂生成的节点.
    // 最后返回最新的树根节点.
    // 上升的节点, 肯定是一个oneSlot 节点
    int InsertNode(Node *pUpNode, Tree &newRoot)
    {
        // 下面节点调用父节点插入上升节点, 父节点为空
        if( NULL == this )
        {
            newRoot = pUpNode;
            return kTREE23_SUC;
        }

        if ( isEmptySlot() )
            return Empty_InsertNode(pUpNode);

        if ( isOneSlot() )
            return InPlace_InsertNode(pUpNode);

        else
            // m_parent 可能为NULL(root节点的根节点为NULL), 可以在这里返回一个新的节点, 作为新的根.
            return Split_InsertNode(pUpNode, newRoot);

        return  kTREE23_UNKNOW_ERR;
    }


    int Empty_InsertNode(Node *pUpNode)
    {
        Slot upSlot = pUpNode->m_leftSlot;

        SetLeftSlot(upSlot);

        SetTree(pUpNode->m_leftTree, m_midTree, NULL);

        delete pUpNode;        // 释放节点.
        return kTREE23_SUC;
    }

    // 在当前节点插入一个下面上升来的节点.(原地还有一个空槽)
    // 上升节点分裂而来, 必定是一个oneSlot 节点
    int InPlace_InsertNode(Node *pUpNode)
    {
        Slot upSlot = pUpNode->m_leftSlot;

        T  inPlaceEle = m_leftSlot.GetEle();
        T  upEle      = upSlot.GetEle();

        if (upEle < inPlaceEle)
        {
            SetSlot(upSlot, m_leftSlot);
            SetTree(pUpNode->m_leftTree, pUpNode->m_midTree, m_rightTree);
        }

        if (upEle > inPlaceEle)
        {
            SetSlot(m_leftSlot, upSlot);
            SetTree(m_leftTree, pUpNode->m_leftTree, pUpNode->m_midTree);
        }

        delete  pUpNode;
        return kTREE23_SUC;
    }

    // 2-3树操作中最复杂的之处: 因为分裂的情况比较多
    // 当前节点无空槽, 分裂当前节点, 插入新节点.
    int Split_InsertNode(Node  *pUpNode, Tree &newRoot)
    {
        Slot upSlot = pUpNode->m_leftSlot;

        T  leftEle  = m_leftSlot.GetEle();
        T  rightEle = m_rightSlot.GetEle();
        T  upEle    = upSlot.GetEle();

        // 先将m_parent保存下来, 下面操作会修改m_parent的值
        PNode originParent = this ->m_parent;

        PNode upSplit;

        if (upEle < leftEle)                             // 上升节点居左.
            upSplit = leftSplit(pUpNode);

        if ( (upEle > leftEle) && (upEle < rightEle) )   // 上升节点居中.
            upSplit = midSplit(pUpNode);

        if ( upEle > rightEle )                          // 上升节点居右.
            upSplit = rightSplit(pUpNode);


        // 最后, 将upSplit 交给父节点处理
        return originParent -> InsertNode(upSplit, newRoot);

        //return Parent_InsertNode(upSplit, newRoot);
    }


    int Parent_InsertNode(Node *pUpNode, Tree &newRoot)
    {
        if ( NULL == m_parent )
        {
            newRoot = pUpNode;
            return kTREE23_SUC;
        }

        return m_parent->InsertNode(pUpNode, newRoot);
    }


private:        // split相关

    PNode leftSplit(Node  *pUpNode)
    {
        ExpNode  expNode;

        // 上升节点居左.
        // 需重构, 分离出新函数.
        Node  *leftSplit  = pUpNode;
        Node  *upSplit    = new Node();
        Node  *rightSplit = this;

        // 抛弃 this 的 m_leftTree: 被细化为 pUpNode 的 m_leftTree + m_midTree
        expNode.Init( pUpNode -> m_leftTree,
                      pUpNode -> m_midTree,
                      this    -> m_midTree,
                      this    -> m_rightTree,

                      pUpNode-> m_leftSlot,
                      this   -> m_leftSlot,
                      this   -> m_rightSlot
                    );


        expNode.Explode(leftSplit, upSplit, rightSplit);
        return  upSplit;
    }

    PNode midSplit(Node  *pUpNode)
    {
        ExpNode  expNode;

        Node *leftSplit  = this;
        Node *upSplit    = pUpNode;
        Node *rightSplit = new Node();

        // this的midTree被抛弃, 被细化成upSplit的m_leftTree + m_midTree
        expNode.Init( this    -> m_leftTree,
                      pUpNode -> m_leftTree,
                      pUpNode -> m_midTree,
                      this    -> m_rightTree,

                      this    -> m_leftSlot,
                      pUpNode -> m_leftSlot,
                      this    -> m_rightSlot
                    );

        expNode.Explode(leftSplit, upSplit, rightSplit);
        return upSplit;
    }

    PNode rightSplit(Node  *pUpNode)
    {
        ExpNode  expNode;
        Node *leftSplit  = this;
        Node *upSplit    = new Node();
        Node *rightSplit = pUpNode;

        // this的m_rightTree被抛弃, 被细化成upSplit的m_leftTree + m_midTree
        expNode.Init( this    -> m_leftTree,
                      this    -> m_midTree,
                      pUpNode -> m_leftTree,
                      pUpNode -> m_midTree,

                      this    -> m_leftSlot,
                      this    -> m_rightSlot,
                      pUpNode -> m_leftSlot
                    );

        expNode.Explode(leftSplit, upSplit, rightSplit);
        return upSplit;
    }


private:    // find 相关

    bool leftFind(T ele, PNode &findNode)
    {
        if ( NULL == m_leftTree )
            return false;

        return m_leftTree->Find(ele, findNode);
    }

    bool rightFind(T ele, PNode &findNode)
    {
        if ( NULL == m_rightTree )
            return false;

        return m_rightTree->Find(ele, findNode);
    }

    bool midFind(T ele, PNode &findNode)
    {
        if ( NULL == m_midTree )
            return false;

        return m_midTree->Find(ele, findNode);
    }


private:    // 判断 + 初始化

    // 两个slot全空
    bool isEmptySlot() {
        return  m_leftSlot.IsEmpty() && m_rightSlot.IsEmpty();
    }

    // 一个slot空, 还有一个slot满.(本代码中是leftSlot已用, rightSlot未用)
    bool isOneSlot() {
        // 既不全空, 也不全满
        return  !( isFullSlot() ||
                   isEmptySlot() );
    }

    // 两个slot全满
    bool isFullSlot() {
        return    !( m_leftSlot.IsEmpty() ||
                     m_rightSlot.IsEmpty() );
    }

    void initResource()
    {
        m_parent    = NULL;
        m_leftTree  = NULL;
        m_midTree   = NULL;
        m_rightTree = NULL;
    }

};

// 爆炸节点, 即一个3节点: 即将被分裂
template <class T>
class  ExplodeNode
{
public:
    typedef Tree23_Node<T>   *Tree;         // 用 Tree23_Node指针类型表示2-3 树.
    typedef Tree23_Node<T>    Node;         // 用 Tree23_Node指针类型表示2-3 树.
    typedef Tree23_Slot<T>    Slot;

public:
    ExplodeNode() {
        //memset(m_mergeTree, 0, sizeof(Tree) * 4);    // m_mergeTree = {NULL};
        memset(m_mergeTree, 0, sizeof(m_mergeTree));    // m_mergeTree = {NULL};
    }

    void Init(Tree t0, Tree t1, Tree t2, Tree t3,
              Slot &ls, Slot &ms, Slot &rs
            )
    {
        m_mergeTree[0] = t0;
        m_mergeTree[1] = t1;
        m_mergeTree[2] = t2;
        m_mergeTree[3] = t3;

        ls.Move2(m_leftSlot );
        ms.Move2(m_midSlot  );
        rs.Move2(m_rightSlot);
    }

    // 开始爆炸吧: 轰, 数据就分裂到了 左 + 右 + 上节点
    void Explode(Node *leftSplit, Node *upSplit, Node *rightSplit)
    {
        // slot re assign
        leftSplit  -> SetLeftSlot(m_leftSlot);
        upSplit    -> SetLeftSlot(m_midSlot);
        rightSplit -> SetLeftSlot(m_rightSlot);

        // subtree re assign
        leftSplit  -> SetTree(m_mergeTree[0], m_mergeTree[1], NULL);
        rightSplit -> SetTree(m_mergeTree[2], m_mergeTree[3], NULL);
        upSplit    -> SetTree(leftSplit     , rightSplit    , NULL);
    }

    // 3 节点上有4棵树, 3个slot
    Tree  m_mergeTree[4];
    Slot  m_leftSlot;
    Slot  m_midSlot;
    Slot  m_rightSlot;
};


template <class T>
class  Tree23_Slot
{
    typedef Tree23_Slot<T>  Slot;

private:
    T       m_ele;          // 元素本身
    bool    m_empty;        // 元素是否可用( 因为没有办法通过节点的子树, 或者元素本身的值判定槽中是否存入了元素.)

public:
    Tree23_Slot() {
        m_empty = true;
    }

    Tree23_Slot(T ele) {
        m_ele   = ele;
        m_empty = false;
    }

    void Show()
    {
        std::cout << m_ele << std::endl;
    }

    void SetEle(T ele) {
        m_ele = ele;
        setFull();
    }

    // copy后, invalidate 当前slot
    void Move2(Slot &to) {
        if (this == &to)    // 避免了同一个对象Move2, 导致setEmpty()的情况.
            return;

        Copy2(to);
        setEmpty();
    }

    // Copy, 就是copy构造函数的功能: 但还是写出来, 和Copy2 相对应.
    void Copy2(Slot &to) const {
        to = *this;
    }

    bool IsEquel(T ele) {
        return ele == m_ele;
    }

    bool IsEmpty() const { return m_empty; }
    T&   GetEle()  { return m_ele; }

private:

    void setEmpty()   { m_empty = true;  }
    void setFull()    { m_empty = false; }
};

#endif   /* ----- #ifndef tree23_H_  ----- */
